package deom2;

public class MyTree {
    public static class BTNode {
        BTNode left;
        BTNode right;
        int value;

        BTNode(int value) {
            this.value = value;
        }
    }
    public BTNode root;

    public BTNode getRoot() {
        return this.root;
    }

    public void createBinaryTree() {
        BTNode node1 = new BTNode(1);
        BTNode node2 = new BTNode(2);
        BTNode node3 = new BTNode(3);
        BTNode node4 = new BTNode(4);
        BTNode node5 = new BTNode(5);
        BTNode node6 = new BTNode(6);

        root = node1;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node4.right = node6;
    }

    //前序遍历
    public void preOrder(BTNode root) {
        if (root == null) return;
        System.out.print(root.value+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历
    public void inOrder(BTNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.value+" ");
        inOrder(root.right);
    }

    //后序遍历
    public void postOrder(BTNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.value+" ");
    }
    /*
    * 获取数中节点个数
    * 1.遍历法
    * 2.子问题法
    * */
    public int nodeSize;

    public void getnodeSize1(BTNode root) {
        if (root == null) return;
        nodeSize++;
        getnodeSize1(root.left);
        getnodeSize1(root.right);
    }
    public int getnodeSize2(BTNode root) {
        if (root == null) return 0;
        return getnodeSize2(root.left) + getnodeSize2(root.right) + 1;
    }

    public int getNodeSize() {
        return this.nodeSize;
    }
    /*
    * 获取叶子节点的个数
    * 1.遍历法
    * 2.子问题法
    * */
    public int leafNodeSize;

    public void getLeafNodeSize1(BTNode root) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            leafNodeSize++;
        }
        getLeafNodeSize1(root.left);
        getLeafNodeSize1(root.right);
    }

    public int getLeafNodeSize2(BTNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeSize2(root.left) + getLeafNodeSize2(root.right);
    }

    /*获取第 k 层的节点个数
    * */
    public int getLevelNodeSize(BTNode root,int k) {
        if (root == null) return 0;
        if (k == 1) return 1;
        return getLevelNodeSize(root.left,k - 1) + getLevelNodeSize(root.right,k - 1);
    }
    /*
    * 获取数的高度
    * */
    public int getTreeHeight(BTNode root) {
        if (root == null) return 0;
        int leftHeihgt = getTreeHeight(root.left);
        int rightHeihgt = getTreeHeight(root.right);
        return Math.max(leftHeihgt,rightHeihgt) + 1;
    }

    /*看树中是否用 key 的值
    * */
    public boolean isHavekey(BTNode root,int key) {
        
    }
}
